
#include <stdio.h>
#include <stdlib.h>

#include "globals.h"
#include "link.h"


link_ref *initLink(void)
{
	link_ref *link;

	/*	A comparison routine must always be provided. */

		link = (link_ref *) malloc (sizeof(link_ref));
		if (link != NULL) {
			link->count = 0;
			link->head = NULL;
			link->middle = NULL;
		}

	return (link);
}

short	sizeOfLinkList(link_ref *link)
{
	if (link != NULL)
		return (link->count);
	else
		return (0);
}

void	killLink (link_ref **link)
{
	link_node	*run1, *run2;
	int			i;
	
	if (link != NULL) {
		/*	Release all the nodes in the tree */

		run1 = (*link)->head;
		for (i = 0; (i < (*link)->count) && (run1 != NULL); i++) {
			run2 = run1->next;
			free(run1->data);
			free(run1);
			run1 = run2;
		}
		
		/* Just to be paranoid, set the item count to 0 -- in case some
		   pointer has survived. */
		   
		(*link)->count = 0;
		
		free (*link);
		*link = NULL;
	}
}

void dumpTree (link_node *node, int level)
{
	if (node != NULL) {
		dumpTree (node->left, level + 1);
		printf ("node at level %d balance %c\n", level, node->balance);
		dumpTree (node->right, level + 1);
	}
}

void	printLink (link_ref *link)
{
	int	i;
	link_node	*run;
	
	if (link == NULL) 
		printf ("Link list does not exist\n");
	else {
		if (link->count == 0)
			printf ("List is empty\n");
		else {
			run = link->head;
			for (i = 1; i <= link->count; i++) {
				printf ("%d -- data %x\n", i, run->data);
				run = run->next;
			}
		}
		dumpTree (link->middle, 1);
	}
}

void addLinkList (link_ref *link, link_node *afterNode, link_node *newNode)
{
	if (afterNode == NULL) {
		newNode->head = True;
		if (link->head != NULL) {
			newNode->next = link->head;
			newNode->prev = (link->head)->prev;
			(link->head)->prev = newNode;
			(link->head)->head = False;
			if (newNode->next->next == newNode->next)
				newNode->next->next = newNode;
		}
		else {
			newNode->tail = True;
			newNode->prev = newNode;
			newNode->next = newNode;
		}
		link->head = newNode;
	}
	else {
		newNode->tail = afterNode->tail;
		afterNode->tail = False;
		newNode->head = False;
		newNode->next = afterNode->next;
		newNode->prev = afterNode;
		if (afterNode->next != NULL)
			(afterNode->next)->prev = newNode;
		afterNode->next = newNode;
	}
}

boolean isAChildOf (link_node *child, link_node *parent)
{
	if ((parent != NULL) && 
		((parent->left == child) || (parent->right == child)))
		return (True);
	else
		return (False);
}

void singlePivot (link_ref *link, link_node *oldRoot, link_node *newRoot)
{
	if ((oldRoot != NULL) && (newRoot != NULL)) {
		if (isAChildOf(newRoot, oldRoot) == True) {
			/*	Put newRoot into oldRoot's place in the tree */

			if (oldRoot->parent != NULL)
				if ((oldRoot->parent)->left == oldRoot)
					(oldRoot->parent)->left = newRoot;
				else
					(oldRoot->parent)->right = newRoot;
			else 
				link->middle = newRoot;
			newRoot->parent = oldRoot->parent;

			if (oldRoot->left == newRoot) {
				/*	Make things right for newRoot's child */

				if (newRoot->right != NULL)
					(newRoot->right)->parent = oldRoot;
				oldRoot->left = newRoot->right;

				/*	Cement the parent/child relationship between newRoot and
					oldRoot */

				newRoot->right = oldRoot;
				oldRoot->parent = newRoot;
			}
			else {
				/*	Make things right for newRoot's child */

				if (newRoot->left != NULL)
					(newRoot->left)->parent = oldRoot;
				oldRoot->right = newRoot->left;

				/*	Cement the parent/child relationship between newRoot and
					oldRoot */

				newRoot->left = oldRoot;
				oldRoot->parent = newRoot;
			}
		}
	}
}

void doublePivot (link_ref *link, link_node *oldRoot, link_node *child, 
link_node *pivot)
{
	if ((oldRoot != NULL) && (pivot != NULL) && (child != NULL)) {
		if ((isAChildOf(child, oldRoot)) && (isAChildOf(pivot, child))) {

			/*	Put pivot into oldRoot's place in the tree */

			if (oldRoot->parent != NULL)
				if ((oldRoot->parent)->left == oldRoot)
					(oldRoot->parent)->left = pivot;
				else
					(oldRoot->parent)->right = pivot;
			else
				link->middle =  pivot;
			pivot->parent = oldRoot->parent;

/*	The 'child' here used to be 'pivot' */
			if (oldRoot->left == child) {
				/*	Make things right for pivot's left child */

				if (pivot->left != NULL)
					(pivot->left)->parent = child;
				child->right = pivot->left;

				/*	Make things right for pivot's right child */

				if (pivot->right != NULL)
					(pivot->right)->parent = oldRoot;
				oldRoot->left = pivot->right;

				/*	Cement the parent/child relationship between pivot,
					child, and oldRoot */

				pivot->left = child;
				pivot->right = oldRoot;

				child->parent = pivot;
				oldRoot->parent = pivot;
			}
			else {
				/*	Make things right for pivot's left child */

				if (pivot->left != NULL)
					(pivot->left)->parent = oldRoot;
				oldRoot->right = pivot->left;

				/*	Make things right for pivot's right child */

				if (pivot->right != NULL)
					(pivot->right)->parent = child;
				child->left = pivot->right;

				/*	Cement the parent/child relationship between pivot,
					child, and oldRoot */

				pivot->left = oldRoot;
				pivot->right = child;

				oldRoot->parent = pivot;
				child->parent = pivot;
			}
		}
	}
}

void addBinaryTree (link_ref *link, link_node *afterNode, link_node *newNode)
{
	link_node	*runNode;

	newNode->balance = EQUAL;
	newNode->left = NULL;
	newNode->right = NULL;

	if (afterNode == NULL) {
		if (link->middle != NULL) {
			/*	Try to find the parent for the node */
			
			runNode = link->middle;
			while (runNode->left != NULL)
				runNode = runNode->left;
			newNode->parent = runNode;
			runNode->left = newNode;
		}
		else {
			newNode->parent = NULL;
			link->middle = newNode;
		}
	}
	else {
		/*	Set up the newNode in the binary tree */
		
		if (afterNode->right == NULL) {
			newNode->parent = afterNode;
			afterNode->right = newNode;
		}
		else {
			runNode = afterNode->right;
			while (runNode->left != NULL)
				runNode = runNode->left;
			newNode->parent = runNode;
			runNode->left = newNode;
		}
	}
}

void setAddBalance (link_node *current, link_node *child, 
link_node *grandchild, int growSide)
{
	if (grandchild != NULL) { 
		grandchild->balance = EQUAL;
		if (growSide == EQUAL) {
			/*	The grandchild was at the bottom of the tree -- all
				nodes are equal. */

			current->balance = EQUAL;
			child->balance = EQUAL;
		}
		else {
			if (grandchild->left == current) {
				current->balance = 
					((growSide == LEFT_HEAVY) ? EQUAL : LEFT_HEAVY);
				child->balance = 
					((growSide == LEFT_HEAVY) ? RIGHT_HEAVY : EQUAL);
			}
			else {
				current->balance = 
					((growSide == LEFT_HEAVY) ? RIGHT_HEAVY : EQUAL);
				child->balance = 
					((growSide == LEFT_HEAVY) ? EQUAL : LEFT_HEAVY);
			}
		}
	}
}

void rebalanceAdd (link_ref *link, link_node *node)
{
	link_node *current, *child, *grandchild;
	boolean	done;
	int	growSide;

	current = node->parent;
	child = node;
	grandchild = NULL;
	growSide = EQUAL;
	done = False;
	for(;(current != NULL) && (done == False);) {
		if (current->balance == EQUAL) {
			if (child == current->left)
				current->balance = LEFT_HEAVY;
			else
				current->balance = RIGHT_HEAVY;
			if (grandchild != NULL) {
				if (child->left == grandchild)
					growSide = LEFT_HEAVY;
				else
					growSide = RIGHT_HEAVY;
			}
			grandchild = child;
			child = current;
			current = current->parent;
		}
		else if (((current->balance == LEFT_HEAVY) && (current->right == child))
			|| ((current->balance == RIGHT_HEAVY) && (current->left == child))){
			current->balance = EQUAL;
			done = True;	
		}
		else if (((current->balance == LEFT_HEAVY) && (current->left == child))
		|| ((current->balance == RIGHT_HEAVY) && (current->right == child))) {
			if (current->right == child) {
				if (grandchild == child->right) {
					singlePivot(link, current, child);
					current->balance = EQUAL;
					child->balance = EQUAL;
				}
				else {
					doublePivot(link, current, child, grandchild);
					setAddBalance (current, child, grandchild, growSide);
				}
			}
			else {
				if (grandchild == child->right) {
					doublePivot(link, current, child, grandchild);
					setAddBalance (current, child, grandchild, growSide);
				}
				else {
					singlePivot(link, current, child);
					current->balance = EQUAL;
					child->balance = EQUAL;
				}
			}
			done = True;
		}
	}
}

boolean	addAfterLink (link_ref *link, link_node *node, void *data, 
	link_node **newNode)
{
	if (link == NULL)
		return (False);
	else {
		/*	By convention, a node of NULL means insert as the first item
			in the list */
			
		*newNode = (link_node *)malloc(sizeof(link_node));
		if (*newNode == NULL)
			return (False);
		else {
			(*newNode)->data = data;

			addLinkList (link, node, *newNode);
			addBinaryTree (link, node, *newNode);
			rebalanceAdd (link, *newNode);
			
			link->count += 1;
			return (True);
		}
	}
}

boolean	addBeforeLink (link_ref *link, link_node *node, void *data,
	link_node	**newNode)
{
	if (link == NULL)
		return (False);
	else {
		/*	The list is implemented as circular so I can always back up by 1 */
		
		if (link->head != NULL)
			if (node == link->head)
				return (addAfterLink (link, NULL, data, newNode));
			else 
				return (addAfterLink (link, node->prev, data, newNode));
		else
			return (addAfterLink (link, NULL, data, newNode));
	}
}

void removeLinkList(link_ref *link, link_node *node)
{
	if (node->head == True) {
		if (node->next != node) {
			link->head = node->next;
			(node->next)->head = True;
		}
		else {
			link->head = NULL;
			link->middle = NULL;
		}
	}
	if (node->next != NULL) {
		if (node->tail == True)
			(node->prev)->tail = True;
		(node->next)->prev = node->prev;
		(node->prev)->next = node->next;
	}

	/*	Just to be sure, kill the pointers left in the node. */

	node->next = NULL;
	node->prev = NULL;
}

void removeBinaryTree (link_ref *link, link_node *node)
{
	link_node	*current, *child;
	link_node	*replacement, *sibling, *sibChild;
	boolean		done, childRelation;
	link_node	*nodeP, *nodeL, *nodeR, *repP, *repL, *repR;

	if ((link != NULL) && (node != NULL)) {
		if (node->right != NULL) {
			replacement = node->right;
			while (replacement->left != NULL)
				replacement = replacement->left;
		}
		else if (node->left != NULL) {
			replacement = node->left;
			while (replacement->right != NULL)
				replacement = replacement->right;
		}
		else 
			replacement = node;

		/*	replacement == node only if node has no children. */

		current = replacement->parent;
		child = replacement;
		for (done = False;(current != NULL) && (done == False);){
			if (current->balance == EQUAL) {
				current->balance = 
					(child == current->left ? RIGHT_HEAVY : LEFT_HEAVY);
				done = True;
			}
			else if (((current->balance == RIGHT_HEAVY) && 
								(current->right == child)) || 
				((current->balance == LEFT_HEAVY) && (current->left == child))) {
				current->balance = EQUAL;
			}
			else if ((current->balance == RIGHT_HEAVY) && 
						(current->left == child)) {
				switch ((current->right)->balance) {
					case EQUAL:
						sibling = current->right;
						singlePivot (link, current, sibling);
						sibling->balance = LEFT_HEAVY;
						done = True;
						break;
					case RIGHT_HEAVY:
						sibling = current->right;
						singlePivot (link, current, sibling);
						current->balance = EQUAL;
						sibling->balance = EQUAL;
						current = sibling;
						break;
					case LEFT_HEAVY:
						sibling = current->right;
						sibChild = sibling->left;
						doublePivot (link, current, sibling, sibChild);
						if (sibChild->balance == EQUAL) {
							current->balance = EQUAL;
							sibling->balance = EQUAL;
						}
						else if (sibChild->balance == RIGHT_HEAVY) {
							current->balance = LEFT_HEAVY;
							sibling->balance = EQUAL;
						}
						else {
							current->balance = EQUAL;
							sibling->balance = RIGHT_HEAVY;
						}
						sibChild->balance = EQUAL;
						current = sibChild;
						break;
					default:
						break;
				}
			}
			else if ((current->balance == LEFT_HEAVY) && 
						(current->right == child)) {
				switch ((current->left)->balance) {
					case EQUAL:
						sibling = current->left;
						singlePivot (link, current, sibling);
						sibling->balance = RIGHT_HEAVY;
						done = True;
						break;
					case LEFT_HEAVY:
						sibling = current->left;
						singlePivot (link, current, sibling);
						current->balance = EQUAL;
						sibling->balance = EQUAL;
						current = sibling;
						break;
					case RIGHT_HEAVY:
						sibling = current->left;
						sibChild = sibling->right;
						doublePivot (link, current, sibling, sibChild);
						if (sibChild->balance == EQUAL) {
							current->balance = EQUAL;
							sibling->balance = EQUAL;
						}
						else if (sibChild->balance == LEFT_HEAVY) {
							current->balance = RIGHT_HEAVY;
							sibling->balance = EQUAL;
						}
						else {
							current->balance = EQUAL;
							sibling->balance = LEFT_HEAVY;
						}
						sibChild->balance = EQUAL;
						current = sibChild;
						break;
					default:
						break;
					}
				}
			child = current;
			current = current->parent;
		}

		/*	Lastly, really exchange 'replacement' and node.  For
			simplicity, store all the pointers from the nodes and then
			assign them as appropriate (in case replacement = node) */

		nodeP = node->parent;
		nodeL = node->left;
		nodeR = node->right;
		repP = replacement->parent;
		repL = replacement->left;
		repR = replacement->right;
		childRelation = isAChildOf(replacement, node);

		/* Start at the bottom.  I know that replacement has a most
			one non-NULL pointer. */

		if (childRelation == False) {
			if (repL != NULL)
				repL->parent = repP;
			else if (repR != NULL)
				repR->parent = repP;
		}

		if (repP != NULL) {
			if (repP->left == replacement)
				repP->left = (repL != NULL ? repL : repR);
			else
				repP->right = (repL != NULL ? repL : repR);
		}

		/*	Now, move replacement into the spot of node */

		if (node != replacement) {
			if (nodeL != NULL)
				nodeL->parent = replacement;
			if (nodeR != NULL)
				nodeR->parent = replacement;
			if (childRelation == True) {
				replacement->right = node->right;
				replacement->left = node->left;
			}
			else {
				replacement->left = nodeL;
				replacement->right = nodeR;
			}

			if (nodeP != NULL) {
				if (nodeP->left == node)
					nodeP->left = replacement;
				else
					nodeP->right = replacement;	
			}
			else {
				link->middle = replacement;
			}
			replacement->parent = nodeP;
			replacement->balance = node->balance;
		}

		/*	Just to be sure, kill the pointers left in the node. */

		node->parent = NULL;
		node->right = NULL;
		node->left = NULL;
	}
}

boolean	deleteLink (link_ref *link, link_node **node, void **data)
{
	if (link == NULL)
		return (False);
	else {
		if (*node == NULL)
			return (False);
		else {
			*data = (*node)->data;
	
			removeLinkList (link, *node);		
			removeBinaryTree (link, *node);

			free (*node);
			link->count -= 1;

			*node = NULL;

			return (True);
		}
	}
}

link_node	*nextLink (link_ref *link, link_node *node)
{
	if (link == NULL)
		return (NULL);
	else {
		if ( (node == NULL) || (node->tail == True) ) 
			return (NULL);
		else 
			return (node->next);
	}
}

link_node	*prevLink (link_ref *link, link_node *node)
{
	if (link == NULL)
		return (NULL);
	else {
		if ( (node == NULL) || (node->head == True) )
			return (NULL);
		else
			return (node->prev);
	}
}

boolean getLinkInfo (link_node *node, void **data)
{
	if (node == NULL) 
		return (False);
	else {
		*data = node->data;
		return (True);
	}
}

link_node   *binSearchLink (link_ref *link, link_node *current, int side)
{
	if (link == NULL)
		return (NULL);
	else if (current == NULL)
		return (link->middle);
	else if (side == LEFT)
		return (current->left);
	else
		return (current->right);
}

